package com.likou;

import java.util.ArrayList;
import java.util.List;

public class q131 {

    List<List<String>> ans = new ArrayList<>();
    List<String> list = new ArrayList<>();

    public List<List<String>> partition(String s) {
        DFS(s, 0);

        return ans;
    }


    private void DFS(String s, int index) {
        if (index >= s.length()) {
            ans.add(new ArrayList<>(list));
            return;
        }

        for (int i = index; i < s.length(); i++) {
            String substring = s.substring(index, i + 1);
            if (isHW(substring)) {
                list.add(substring);
                DFS(s, i + 1);
                list.remove(list.size() - 1);
            }
        }

    }

    private boolean isHW(String substring) {
        int mid = substring.length() / 2;
        for (int i = 0; i < mid; i++) {
            if (substring.charAt(i) != substring.charAt(substring.length() - 1 - i)) {
                return false;
            }
        }

        return true;
    }
}
